⟸ Go Back ⟸

Exercise 7 (Homework 2).

(regular languages, homomorphism, minimization of DFAs)

Inverse homomorphism of a regular language is regular

1. Show that L=\{w \in \{0,1\}^* \mid \mathtt{value}_2(w)\in 3\mathbb N\} is a regular language. Compute explicitly the minimum DFA for the language \sigma^{-1}(L), where \sigma: \{a,b,c\}\to \{0,1\} is the homomorphism defined by

   1. \sigma(a)=01,
      \sigma(b)=0, and
      \sigma(c)=\lambda.
   2. \sigma(a)=10,
      \sigma(b)=0, and
      \sigma(c)=\lambda.
   3. \sigma(a)=00,
      \sigma(b)=11, and
      \sigma(c)=\lambda.
   4. \sigma(a)=001,
      \sigma(b)=101, and
      \sigma(c)=0.
   Recall that, given a DFA A and a homomorphism \sigma, it is possible to construct a DFA A' recognizing the language \sigma^{-1}(L(A)) as follows: on input w, A' will run A on input \sigma(w) and accept if A does.

2. Given a DFA A and a morphism \sigma, what is the cost of constructing a DFA for the language \sigma^{-1}(L(A))?

3. Does the construction used to obtain the DFA for \sigma^{-1}(L(A)) give us a minimum DFA if we started with a minimum DFA A?

4. Does the construction used to obtain the DFA for \sigma^{-1}(L(A)) still work if we started with an NFA A?